package com.test;

import java.util.*;

public class NumCode {
    private int length = 9;                 //数码长度，可以处理非八数码，例如十五数码
    private int row = 3;                        //行数
    private int col = 3;                        //列数
    private int initArr[];              //初始状态的八数码
    private int targetArr[];            //目标状态的八数码

    public NumCode() {
    }

    public NumCode(int[] initArr, int[] targetArr) throws Exception {
        setInitArr(initArr);
        setTargetArr(targetArr);
    }

    public NumCode(int row, int col, int[] initArr, int[] targetArr) throws Exception {
        setRowAndCol(row,col);
        setInitArr(initArr);
        setTargetArr(targetArr);
    }

    //设置列数和行数
    public void setRowAndCol(int row,int col){
        this.row = row;
        this.col = col;
        this.length = row * col;
    }

    //其实还应该检验输入的数据是否符合情况
    public void setInitArr(int[] initArr) throws Exception {

        if(initArr.length != length)
            throw new Exception("起始数组长度错误!规定长度"+length+",起始数组长度"+initArr.length);
        this.initArr = initArr;

    }

    public void setTargetArr(int[] targetArr) throws Exception {

        if(targetArr.length != length)
            throw new Exception("目标数组长度错误!规定长度"+length+",目标数组长度"+targetArr.length);
        this.targetArr = targetArr;

    }

    /**
     * @Description 通过求逆序值，判断是否有解
     * @return
     **/
    private boolean isSolveable(){
        int reverse = 0;
        for(int i=0;i<length;i++){
            for(int j=0;j<i;j++){
                if(initArr[i] != 0){
                    if(initArr[j] > initArr[i])
                        reverse++;
                }
                if(targetArr[i] != 0){
                    if(targetArr[i] > targetArr[j])
                        reverse++;
                }

            }
        }
        if(reverse % 2 == 0)
            return true;
        return false;
    }

    /**
     * @Description         获取空格移位后的数码
     * @param curArr        当前数码
     * @param emptyIndex    当前数码空格位置
     * @param pos           空格偏移量
     * @return              返回移位后的数码
     **/
    private int[] move(int curArr[],int emptyIndex,int pos){
        int []nextArr = new int[length];
        System.arraycopy(curArr,0,nextArr,0,length);
        int temp;
        temp = nextArr[emptyIndex];
        nextArr[emptyIndex] = nextArr[emptyIndex + pos];
        nextArr[emptyIndex + pos] = temp;

        return nextArr;
    }

    /**
     * @Description         计算当前数码交换前和交换后的“不在位”的数码个数之差
     * @param curArr        当前数码
     * @param emptyIndex    当前数码空格位置
     * @param pos           空格偏移量
     **/
    private int differ(int curArr[],int emptyIndex,int pos){
        //判断移动前，空格位置和目标位置的元素和目标状态的八数码对应元素是否相同
        boolean beforeEmpty = curArr[emptyIndex] == targetArr[emptyIndex];
        boolean beforeTarget = curArr[emptyIndex + pos] == targetArr[emptyIndex + pos];

        //移位前，都是正确的，移位后肯定都错位
        if(beforeEmpty && beforeTarget)
            return 2;

        //移位前，有一个正确的，移位后肯定都错位
        else if(beforeEmpty || beforeTarget)
            return 1;

        //移位前都错位，再判断移位后的情况
        else{
            //判断移动后，空格位置和目标位置的元素和目标状态的八数码对应元素是否相同
            boolean afterEmpty = curArr[emptyIndex] == targetArr[emptyIndex + pos];
            boolean afterTarget = curArr[emptyIndex + pos] == targetArr[emptyIndex];
            if(afterEmpty && afterTarget)
                return -2;
            else if (afterEmpty || afterTarget)
                return -1;
            else
                return 0;
        }
    }


    private Node run() throws Exception {
        if(targetArr.length != length)
            throw new Exception("目标数组长度错误!规定长度"+length+",目标数组长度"+targetArr.length);
        if(targetArr.length != length)
            throw new Exception("目标数组长度错误!规定长度"+length+",目标数组长度"+targetArr.length);
        //如果无解
        if(!isSolveable())
            return null;

        //open表
        Queue<Node> openQueue = new PriorityQueue<>(new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                if(o1.evaluation > o2.evaluation)
                    return 1;
                else if(o1.evaluation < o2.evaluation)
                    return -1;
                return 0;
            }
        });

        int emptyIndex=0;     //记录空格的位置
        int misposition=0;    //数码不在位的个数
        for (int i = 0; i < length; i++) {
            if(initArr[i] == 0){
                emptyIndex = i;
            }
            if(initArr[i] != targetArr[i])
                misposition++;

        }
        Node initNode = new Node(initArr,misposition,emptyIndex,null);
        openQueue.add(initNode);
        //close表
        Set<Node> closeSet = new TreeSet<>();

        while (!openQueue.isEmpty()){
            Node curNode = openQueue.poll();

            //当前节点是目标节点
            if(curNode.misposition == 0){
                return curNode;
            }

            int mispositionOfCur = curNode.misposition;//当前节点“不在位”的个数
            int emptyIndexOfCur = curNode.emptyIndex;   //当前节点空格位置

            //左移
            if(emptyIndexOfCur % this.col > 0){
                int nextArr[] = move(curNode.num,emptyIndexOfCur,-1);
                int differNum = differ(curNode.num,emptyIndexOfCur,-1);
                Node nextNode = new Node(nextArr,differNum + mispositionOfCur,emptyIndexOfCur -1,curNode);
                if(!closeSet.contains(nextNode)){
                    openQueue.add(nextNode);
                }
            }
            //上移
            if(emptyIndexOfCur > this.col){
                int nextArr[] = move(curNode.num,emptyIndexOfCur,-this.col);
                int differNum = differ(curNode.num,emptyIndexOfCur,-this.col);

                Node nextNode = new Node(nextArr,differNum + mispositionOfCur,emptyIndexOfCur - this.col,curNode);
                if(!closeSet.contains(nextNode)){
                    openQueue.add(nextNode);
                }
            }
            //右移
            if(emptyIndexOfCur % this.col < this.col - 1){
                int nextArr[] = move(curNode.num,emptyIndexOfCur,1);
                int differNum = differ(curNode.num,emptyIndexOfCur,1);
                Node nextNode = new Node(nextArr,differNum + mispositionOfCur,emptyIndexOfCur + 1,curNode);
                if(!closeSet.contains(nextNode)){
                    openQueue.add(nextNode);
                }
            }
            //下移
            if (emptyIndexOfCur < length - this.col){
                int nextArr[] = move(curNode.num,emptyIndexOfCur,this.col);
                int differNum = differ(curNode.num,emptyIndexOfCur,this.col);
                Node nextNode = new Node(nextArr,differNum + mispositionOfCur,emptyIndexOfCur +this.col,curNode);
                if(!closeSet.contains(nextNode)){
                    openQueue.add(nextNode);
                }
            }

            closeSet.add(curNode);

        }
        return null;

    }

    /**
     * @Description 将一个一维数组打印成二维数组
     * @param arr   一维数组
     * @return
     **/
    private void print(int []arr){
        for (int j = 0; j < this.row; j++) {
            for (int k = 0; k < this.col; k++) {
                System.out.printf("%3d",arr[j * this.col + k]);
            }
            System.out.println();
        }
    }
    public void show() throws Exception {
        System.out.println("初始数码：");
        print(initArr);
        System.out.println("目标数码：");
        print(targetArr);

        Node curNode = run();
        if (curNode== null){
            System.out.println("无解");
            return;
        }
        List<int[]> path = new ArrayList<>();
        while (curNode != null){
            path.add(curNode.num);
            curNode = curNode.parent;
        }

        for (int i = path.size()-1,index = 0; i >= 0; i--,index++) {
            System.out.println("Step(" + index + "):");
            print(path.get(i));
        }
        System.out.println("----------------------------------------------------");
    }



}

